home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / node_partition1.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  1.5 KB  |  87 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  node_partition1.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_NODE_PARTITION_H
  17. #define LEDA_NODE_PARTITION_H
  18.  
  19. #include <LEDA/graph.h>
  20.  
  21.  
  22. class node_partition {
  23.  
  24. public:
  25.  
  26. void init(const graph& G) 
  27. { init_node_data1(G,nil); 
  28.   node v;
  29.   forall_nodes(v,G) v->data[0] = 1;
  30. }
  31.  
  32.  node_partition(const graph& G) { init(G); }
  33. ~node_partition()               {}   
  34.  
  35. /*
  36. node find(node v) 
  37. { node r = v;
  38.   while (r->data[1]) r = node(r->data[1]); 
  39.   while (v->data[1]) 
  40.   { node u = v;
  41.     v = node(v->data[1]); 
  42.     u->data[1] = r;
  43.    }
  44.   return r;
  45.  } 
  46. */
  47.  
  48. node find(node v) 
  49. { while (v->data[1]) v = node(v->data[1]); 
  50.   return v;
  51.  }
  52.  
  53. int  same_block(node v, node w)   { return find(v) == find(w); }
  54.  
  55. void union_blocks(node v, node w) 
  56. { node x = find(v);
  57.   node y = find(w);
  58.   if (x != y) 
  59.     if (int(x->data[0]) <  int(y->data[0]))
  60.       { x->data[1] = y; 
  61.         (int&)y->data[0] += int(x->data[0]);
  62.        }
  63.     else
  64.       { y->data[1] = x; 
  65.         (int&)x->data[0] += int(y->data[0]);
  66.        }
  67.     
  68. }
  69.  
  70. void set_inf(node v, node w) 
  71. { if (v->data[1])
  72.   { node r = find(v); 
  73.     v->data[1] = nil; 
  74.     r->data[1] = v; 
  75.     v->data[0] = r->data[0];
  76.    }
  77.  }
  78.  
  79.  
  80. node operator()(node v) { return find(v); }
  81.  
  82.  
  83. };
  84.  
  85.  
  86. #endif
  87.